The present invention relates generally to cryptographic methods and, more particularly, to methods of establishing an encryption key between two or more parties.
Encryption is the process of disguising intelligible information, called plaintext, to hide its substance from eavesdroppers. Encrypting plaintext produces unintelligible data called ciphertext. Decryption is the process of converting ciphertext back to its original plaintext. Using encryption and decryption, two parties can send messages over an insecure channel without revealing the substance of the message to eavesdroppers.
A cryptographic algorithm or cipher is a mathematical function used in the encryption and decryption of data. A cryptographic algorithm works in combination with a key to encrypt and decrypt messages. The key, typically a large random number, controls the encryption of data by the cryptographic algorithm. The same plaintext encrypts to different ciphertext with different keys. In general, it is extremely difficult to recover the plaintext of a message without access to the key, even by an eavesdropper having full knowledge of the cryptographic algorithm.
One type of key-based cryptographic algorithm is a symmetric algorithm, also called secret key algorithms, in which the same key is used both for encryption and decryption. Symmetric algorithms require that the sender and receiver of the message agree on a secret key before they can communicate securely. One benefit of symmetric algorithms is that symmetric algorithms are fast. However, key distribution can be a problem, particularly where the communicating parties are in different physical locations. The parties must agree upon a key in secret, since anyone possessing the key can encrypt or decrypt messages. If the key is compromised, an eavesdropper can decrypt any messages encrypted to that key. The eavesdropper could also pretend to be one of the parties and produce false messages to fool the other party.
The Diffie-Hellman algorithm is a key exchange algorithm that allows two or more parties to agree on a secret key over an insecure channel without divulging the secret key. According to the Diffie-Hellman algorithm, the parties agree on two, non-secret prime numbers P1 and P2 which may be chosen at random with P2 being typically a large prime number. The security of the system is based on the difficulty of factoring numbers as large as P2. Each party generates a large random integer, denoted X1 and X2, respectively. The parties then calculate exchanged numbers Y1 and Y2, respectively. The first party computes Y1 using the equation Y2=P1X1 mod P2. The second party computes Y2 using the equation Y2=P1X2 mod P2. The first party transmits Y1 to the second party and second party transmits Y2 to the first party. The first party computes the key K using the K=Y2X1 mod P2. The second party computes the key K using the equation K=Y1X2 mod P2. Since Y2X1 mod P2 and Y1X2 mod P2 both equal P1X1X2 mod P2, both parties compute the same key K. However, an eavesdropper cannot compute the key K with knowledge of only of P1, P2, Y1, and Y2. Therefore, the value K, which was computed independently by the two parties using information exchanged over the insecure channel, may be used by the parties as the secret key K for secure communications.
Typically, the parties using the Diffie-Hellman algorithm take turns exchanging information. Information sent in one direction triggers a response to be sent in the reverse direction until the encryption key is established. However, the second party normally receives the exchanged number Y1 from the first party prior to the first party receiving the exchanged number Y2 in return. Thus, the second party is in position to determine the encryption key K by combining the exchanged number received from the first party with the locally generated random number before the first party has received enough information to do likewise. Moreover, the second party can examine the encryption key K and decide that it does not suit a nefarious purpose and thus continue to generate further local random numbers until one is found that results in a desired encryption key K.
The present invention establishes an encryption key between two or more parties in a manner that prohibits any party from forcing the value of the key to a desired value. The encryption key is based on exchanged values derived by each of the parties from random bitstrings. By incrementally sharing the exchanged values, the final value of the encryption key cannot be forced by one party to a certain value.
In one embodiment, the first party generates a first random number and computes a first exchanged number based on the first random number. The first exchanged number is split into at least two parts, with less than the total number of parts being sent to the second party to initiate a secure communication session. The second party generates a second random number, and then computes a second exchanged number based on the second random number. Because the second party does not yet have the remainder of the first exchanged number, the second party cannot choose a value for the second exchanged number that will force the encryption key to a desired value. The second exchanged number is then sent to the first party. The first party may then compute the encryption key. However, because the first party has already sent the second party a part of the first exchanged number, the first party likewise cannot force the value of the encryption key to a desired value. The first party sends the second party the remainder of the first exchanged number so that the second party can also determine the encryption key only after receiving at least a part of the second exchanged number.
More than two parties may take part in the establishment of the encryption key. Additionally, the exchanged numbers of each party may be split into more than two sections to further enhance the security of the key exchange procedure.